package class18;

/**
 * @author YZY
 * @since 2022/8/18 11:16
 * <a href="https://leetcode.cn/problems/predict-the-winner/">486. 预测赢家</a>
 */
public class Code02_CardsInLine {

    // 暴力尝试
    public static int cardsInLine1(int[] arr) {
        int f = f1(arr, 0, arr.length - 1);
        int l = s1(arr, 0, arr.length - 1);
        return Math.max(f, l);
    }

    private static int f1(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L];
        }
        int left = arr[L] + s1(arr, L + 1, R);
        int right = arr[R] + s1(arr, L, R - 1);
        return Math.max(left, right);
    }

    private static int s1(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int left = f1(arr, L + 1, R);
        int right = f1(arr, L, R - 1);
        return Math.min(left, right);
    }

    // 记忆化搜索
    public static int cardsInLine2(int[] arr) {
        int n = arr.length;
        int[][] fdp = new int[n][n];
        int[][] sdp = new int[n][n];
        int first = f2(arr, fdp, sdp, 0, n - 1);
        int second = s2(arr, fdp, sdp, 0, n - 1);
        return Math.max(first, second);
    }

    private static int f2(int[] arr, int[][] fdp, int[][] sdp, int L, int R) {
        if (fdp[L][R] != 0) {
            return fdp[L][R];
        }
        if (L == R) {
            return arr[L];
        }
        int left = arr[L] + s2(arr, fdp, sdp, L + 1, R);
        int right = arr[R] + s2(arr, fdp, sdp, L, R - 1);
        return fdp[L][R] = Math.max(left, right);
    }

    private static int s2(int[] arr, int[][] fdp, int[][] sdp, int L, int R) {
        if (sdp[L][R] != 0) {
            return sdp[L][R];
        }
        if (L == R) {
            return 0;
        }
        int left = f2(arr, fdp, sdp, L + 1, R);
        int right = f2(arr, fdp, sdp, L, R - 1);
        return sdp[L][R] = Math.min(left, right);
    }

    // 动态规划
    public static int cardsInLine3(int[] arr) {
        int n = arr.length;
        int[][] fdp = new int[n][n];
        int[][] sdp = new int[n][n];
        for (int col = 0; col < n; ++col) {
            fdp[col][col] = arr[col];
        }
        for (int col = 1; col < n; ++col) {
            for (int L = 0, R = col; R < n; ++L, ++R) {
                fdp[L][R] = Math.max(arr[L] + sdp[L + 1][R], arr[R] + sdp[L][R - 1]);
                sdp[L][R] = Math.min(fdp[L + 1][R], fdp[L][R - 1]);
            }
        }
        return Math.max(fdp[0][n - 1], sdp[0][n - 1]);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7};
        System.out.println(cardsInLine1(arr));
        System.out.println(cardsInLine2(arr));
        System.out.println(cardsInLine3(arr));
    }

}
